Computer programs are groups of instructions that describe actions to be performed by a computer or other processor-based device. When a computer program is loaded and executed on computer hardware, the computer will behave in a predetermined manner by following the instructions of the computer program. Accordingly, the computer becomes a specialized machine that performs the tasks prescribed by the instructions.
In the early years of computing, sets of instructions or programs were relatively small. Over time, programs continue to expand in both length and complexity. Even with processing power and other hardware capacity doubling every twelve months in accordance with Moore's Law, some programs are constrained or limited by their hardware counterparts. Moreover, problems can exist for execution of extensive programs on resource sensitive systems such as mobile devices (e.g., phones, palmtop computers, music players . . . ). Various technologies are consequently employed to facilitate program execution within a given environment.
Memoization is one conventionally employed optimization technique for expediting program execution. Upon initial function evaluation, results are stored or cached for subsequent use. The next time a function is called with the same parameters, a cached result can be immediately returned rather than re-computing the result anew. Many computations can be made significantly more efficient by remember results of previous computations. In effect, memoization involves a runtime trade-off of memory space for execution speed.
A typical example of memoization involves the Fibonacci function, which identifies a sequence of numbers whose values are the sum of the previous two values following two starting values. In particular, the function can be defined as follows:
Fib(1)=1
Fib(2)=1
Fib(n)=Fib(n−1)+Fib(n−2)
If the definition for Fib(n−1) in the last line is unfolded, the result is:
                              Fib          ⁡                      (            n            )                          =                              Fib            ⁡                          (                              n                -                1                -                1                            )                                +                      Fib            ⁡                          (                              n                -                1                -                2                            )                                +                      Fib            ⁡                          (                              n                -                2                            )                                                              =                              Fib            ⁡                          (                              n                -                2                            )                                +                      Fib            ⁡                          (                              n                -                3                            )                                +                      Fib            ⁡                          (                              n                -                2                            )                                          As shown, there are redundant computations, namely Fib(n−2). In fact, an exponential number of steps is required to compute the Fib(n) (viz. O(cn)). By modifying the Fibonacci function to cache or memoize previous computations, the function can run in linear time (viz. O(n)).
Functions or procedures are conventionally memorized manually by programmers. An assessment is initially made regarding whether or not it would be beneficial to memoized a function. Subsequently, a function can be rewritten in memorized form where desired. Alternatively, a new memoized function can be generated and targeted by calls previously designating the original version.